package top.wanzc.java.basic.sort;

import java.util.Arrays;

/**
 * ϣ������
 * @author zhengchong.wan
 *
 */
public class ShellSortDemo {
	
	public static void main(String[] args) {
		int a[] = {0, 49, 38, 65, 97, 76, 13, 27, 49, 0, 0, 0, 0, 0};
		// �ٶ�a�ĳ���Ϊ8
		sort(a, 8);
		System.out.println(Arrays.toString(a));
	}
	
	private static void sort(int[] a, int n) {
		int d, i, j;
		for (d = n / 2; d >= 1; d = d / 2) {
			for (i = d + 1; i <= n; i++) {
				if (a[i] < a[i - d]) {
					a[0] = a[i];
					for (j = i - d; j > 0 && a[0] < a[j]; j -= d) {
						a[j + d] = a[j];
					}
					a[j + d] = a[0];
				}
			}
		}
		a[0] = 0;
	}

}
